package leetcode.array;

import java.util.HashSet;
import java.util.Set;

/**
 * 一个长度为 n + 1 的整形数组，其中的数字都在 1 到 n 之间，包括 1 和 n ，可知至少有一个重复的数字存在。假设只有一个数字重复，找出这个重复的数字。
 * <p>
 * 注意：
 * <p>
 * 不能更改数组内容（假设数组是只读的）。
 * 只能使用恒定的额外空间，即要求空间复杂度是 O(1) 。
 * 时间复杂度小于 O(n2)
 * 数组中只有一个数字重复，但它可能不止一次重复出现。
 */
public class Solution1 {
    public int findDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.contains(num)) {
                set.add(num);
            } else {
                return num;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0, 4, 3, 0};
        int target = 0;
        int result = new Solution1().findDuplicate(nums);
        System.out.println(result);
    }
}
